﻿#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>



//<1>第一个函数递归
//int main()
//{
//
//	printf("hehe");
//	main();//函数自己调用自己，就是递归
//			//但这边是死递归，会一直打印hehe，直到虚拟内存（编译器给变量申请的空间都是虚拟的）不够用，导致的栈溢出
//	return 0;
//}



//<2>求n的阶乘（使用递归）
//int Fact(n)
//{
//	if (n == 0)
//	{
//		return 1;
//	}
//	else
//	{
//		return n * Fact(n - 1);//函数递归的实现过程：比如输入3，求3！
//					//3*Fact(2)-->2*Fact(1)-->1*Fact(0)-->return 1;-->return 1*1=1;-->return 1*2=2;-->return 2*3=6-->return 6;-->main()-->int r
//	}				//先递推，递推到每一个下个Fact(),化解问题，直到化解不了问题，停止递推；再回归，回归到每一个上个Fact()函数，直到回归到main()函数中
//					//递推是靠Fact(),回归是靠return 
//
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);//这里不能输入较大的值，比如100，计算100！会递归出100个递归函数，而每次递归都会申请内存，递归函数太多，内存不够用，会导致栈溢出
//	int r = Fact(n);
//	printf("%d ", r);
//
//	return 0;
//}



#include <string.h>
//<4>顺序打印⼀个整数的每⼀位,比如1234，打印：1 2 3 4
//void print(int n)
//{
//	int arr[10] = { 0 };//这边数组要定义长度，不然默认长度为1（初始化内容的长度）
//	int i = 0;//下标
//	//int g = strlen(n); 错误的，strlen打印字符串的长度
//	int g = 0;
//	int tmp = n;
//	while (tmp)
//	{
//		g++;//用g来表示一个数有几位，每加一个位数，就去掉该数的最后一位，到最后，最高位去掉时，加一个位数，该数变成了0，循环停止
//		tmp /= 10;//去掉一个数的最后一位
//	}
//
//	int k = 0;
//	while (n)//给数组存值
//	{
//		arr[k++] = n % 10;//k++先使用，再++
//		n = n / 10;//%10留最后一位，/10去掉最后一位，直到最后一位被去掉，变成0，循环结束
//	}
//	//k = 3			
//	for (k = g - 1; k >= 0; k--)
//	{
//		printf("%d ", arr[k]);//从数组后面的元素开始打印，直到下标为0
//	}
//
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	print(n);
//
//	return 0;
//}

//（2）方案2，递归函数
//void Print(int n)
//{
//	if (n > 9)
//	{
//		Print(n / 10);//递归函数分为两个部分，即递推和回归
//		//比如n = 1234，进入Print函数，Print(1234)-->Print(123)-->Print(12)-->Print(1)-->printf(1)-->printf(2)-->printf(3)-->printf(4)
//	}	//递推的是递归函数中调用递归函数之前以及含本身的代码，因为递归函数得先执行完
//		//回归的是递归函数中调用递归函数之后的代码，因为递归函数先执行，就会有每个递归函数中调用递归函数后的一段代码没有执行，当递归函数执行完（不符合条件，不再递归）
//		//就会跳出递归函数中的调用递归函数的之前以及本身的代码，执行后面的代码，执行完一个递归函数的代码，就会返回上一个递归函数继续执行后一段的代码
//		//然后执行完递归函数的代码，再到main函数中，直到程序结束，回归的过程其实就是程序继续往下执行的过程
//		//所以递归函数一定是先递推，再回归，递推完成了，才会回归，而不是边递推，边回归，因为逻辑实现上，就是会先执行递归
//	printf("%d ", n % 10);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	Print(n);
//
//	return 0;
//}



//<5>斐波那契数列：求第n个斐波那契数
			//斐波那契数：前两个数字相加之和
//int Print(int n)
//{
//	if (n < 3)
//	{
//		return 1;
//	}
//	else
//	{
//		return Print(n - 1) + Print(n - 2);//求第n个斐波那契数可以用递归函数，但是需要大量计算，并且运行内存足够
//											//因为斐波那契数的公式为：Fib(n) = Fib(n-1)+Fib(n-2)
//											//要算出第n个斐波那契数就要前面两个数相加，而前面两个数的每一个数又要他的前面的两个数相加
//											//所以如果从n开始为数的第一行，那么第一行的数字有2^0个，第二行有2^1个，以此类推
//			//那如果要计算第50个斐波那契数，最底下一行（第50行）的数字就要算到2^50次方（实际上并没有2^50个，因为最右列的数字只能算到第25行就没有了）
//			//所以斐波那契数的计算可以看成一个残缺的金字塔
//			//虽然程序的执行都是从第一列开始的，（因为先要执行完递推的语句）计算完第一列，才会往右边的列继续计算，
//			//实际上递归的函数最多只有50个，并向右不断减少，直到最少25个
//			//所以说明递归函数求斐波那契数确实需要一定的运行内存，但没有想的那么大
//	}		//但是用递归函数的方式需要大量的计算，程序很难跑得动
//
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int r = Print(n);
//	printf("%d ", r);
//
//	return 0;
//}

//（2）方案2
//int Print(int n)
//{
//	int a = 1;//第一个斐波那契数
//	int b = 1;//第二个斐波那契数
//	int c = 1;//n如果小于3，就是求第一个或第二个斐波那契数，且n不会进入循环，那么直接初始化c为1，不进入循环直接返回c
//	while (n >= 3)//要从第三个数开始才算求斐波那契数，前面两个数已经给出
//	{
//		c = a + b;//前两个数的相加为一次计算，如果求第5个斐波那契数，就要3次计算
//		a = b;//为下一次计算做准备，淘汰上一次计算的最前的数，因为求斐波那契数只要之前的最后2个数相加
//		b = c;//把最新的值赋给上一个值
//		n--;//循环的限制条件，也是会减到相应的求第几个斐波那契数该有的次数循环
//			//比如说求第5个斐波那契数，只要3个循环（3次计算）就可以
//			//因为每次循环（计算）只会增加1个数，说明一次循环（计算）只会在数列中前进1个数的进度
//			//而斐波那契数列的前2个数是已经给出的，不需要循环，说明前面两个数的进度已经有了，进度从第3个数开始
//	}		//所以循环（计算）的次数=要求的斐波那契数（n）-已经给出的斐波那契数（2）
//			//所以就解释了为什么这边是n--；而不是n= n -2;n = n - 3;之类的，也就解决了求第n个斐波那契数需要多少次循环的问题
//	return c;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int r = Print(n);
//	printf("%d ", r);
//
//	return 0;
//}